def pasos(u,v):
	n,m=len(u),len(v)
	M1=range(m+1)
	M2=[1]*(m+1)
	for i in range(1,n+1):
		M2[0]=i
		for j in range(1,m+1):
			M2[j]=min(M2[j-1]+1, M1[j]+1, M1[j-1]+(u[i-1]!=v[j-1] and 1 or 0))
		M1=M2[:]
		print ''.join([str(x) for x in M1])
	return M1[m]

print pasos('abc','abx')
